#include "sort.hpp"
void Testop()
{
    srand((unsigned int)time(0));
    const int N = 100000;
    int *a1 = (int *)malloc(sizeof(int) * N);
    int *a2 = (int *)malloc(sizeof(int) * N);
    int *a3 = (int *)malloc(sizeof(int) * N);
    int *a4 = (int *)malloc(sizeof(int) * N);
    // int* a5 = (int*)malloc(sizeof(int) * N);
    // int* a6 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        // a5[i] = a1[i];
        // a6[i] = a1[i];
    }
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();

    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();

    int begin3 = clock();
    SelectSort(a3, N);
    int end3 = clock();

    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();

    // int begin5 = clock();
    // BubbleSort1(a5, N);
    // int end5 = clock();

    // int begin6 = clock();
    // QuickSortNonR(a6,N);
    // int end6 = clock();
    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    // printf("BubbleSort:%d\n", end5 - begin5);
    // printf("QuickSort:%d\n", end6 - begin6);

    free(a1);
    free(a2);
    free(a3);
    free(a4);
    // free(a5);
    // free(a6);
}
void TestInsertSort()
{
    int a[] = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25};
    InsertSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}
void TestShellSort()
{
    int a[] = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25};
    ShellSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}
void TestSelectSort()
{
    int a[] = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25, 23, 19, 50, 2};
    SelectSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}
void TestSelectSort1()
{
    int a[] = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25, 23, 19, 50, 2};
    SelectSort1(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}
void TestHeapSort()
{
    int a[] = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25, 23, 19, 50, 2};
    HeapSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}
void TestBubbleSort()
{
    vector<int> v = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25, 23, 19, 50, 2};
    BubbleSort(v);
    PrintArray1(v);
}
void TestBubbleSort1()
{
    vector<int> v = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25, 23, 19, 50, 2};
    BubbleSort1(v);
    PrintArray1(v);
}
void TestBubbleSort2()
{
    vector<int> v = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25, 23, 19, 50, 2};
    BubbleSort2(v);
    PrintArray1(v);
}
void TestQuickSort1()
{
    // vector<int> v = {3, 5, 2, 7, 8, 6, 1, 9, 4, 0, 13, 16, 10, 15, 11, 14, 12, 25, 23, 19, 50, 2};
    // vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    vector<int> v = {15, 14, 13, 12, 7, 7, 7, 7, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    QuickSort1(v, 0, v.size() - 1);
    PrintArray1(v);
}
int main()
{
    // TestInsertSort();
    // TestShellSort();
    // TestSelectSort();
    // TestSelectSort1();
    // TestHeapSort();
    // TestBubbleSort();
    // TestBubbleSort1();
    // TestBubbleSort2();
    TestQuickSort1();
    // Testop();
    return 0;
}